package com.zp.self.module.level_4_算法练习.算法.二分查找;

import java.util.Arrays;

/**
 * @author By ZengPeng
 */
public class 力扣_167_两数之和II输入有序数组 {
    //测试
    public static void main(String[] args) {

        System.out.println(Arrays.toString(new 力扣_167_两数之和II输入有序数组().twoSum(new int[]{2,7,11,15},9)));
        System.out.println(Arrays.toString(new 力扣_167_两数之和II输入有序数组().twoSum(new int[]{2,3,4},6)));
        System.out.println(Arrays.toString(new 力扣_167_两数之和II输入有序数组().twoSum(new int[]{-1,0},-1)));
        System.out.println(Arrays.toString(new 力扣_167_两数之和II输入有序数组().twoSum(new int[]{1,1},2)));
    }

    /**
     * 题目：给定一个已按照 非递减顺序排列  的整数数组 numbers ，
     * 请你从数组中找出两个数满足相加之和等于目标数 target 。
     * 函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，
     * 所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
     * 你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
     *
     示例 1：
     输入：numbers = [2,7,11,15], target = 9
     输出：[1,2]
     解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
     *
     * 提示：
     * 2 <= numbers.length <= 3 * 104
     * -1000 <= numbers[i] <= 1000
     * numbers 按 非递减顺序 排列
     * -1000 <= target <= 1000
     * 仅存在一个有效答案
     *
     * 分析：【P ♥♥♥】
     *      0.双循环 时间复杂度 O(n*n)
     *      1.HashMap存储： <target-numbers[i],i+1> ,依次遍历是否存在key  .时间、空间复杂度 O(n)
     *      2.双指针：在数字中查找是否有target-numbers[i]  。  时间复杂度O(n)
     *      3.二分法：这个二分法比较的特殊，因为是判断两端值的和与目标值的关系。时间复杂度 O(1) 、空间复杂度 O(logn)
     *                left  + mid > target  : 说明目标在左
     *                left  + mid < target < right + mid : 说明目标不确定
     *                right + mid < target  : 说明目标在右
     *      *题解：双指针？
     * 边界值注意：
     *      1.
     **/
    public int[] twoSum(int[] numbers, int target) {
        //3.二分法：这个二分法比较的特殊，因为是判断两端值的和与目标值的关系。
        int left =0,right=numbers.length-1,mid;
        while (left<right){
            mid= left+(right-left)/2;
            if(numbers[left]+numbers[mid]>target)
                right=mid-1;
            else  if(numbers[right]+numbers[mid]<target)
                left=mid+1;
            else  if(numbers[left]+numbers[right]>target)
                right--;
            else  if(numbers[left]+numbers[right]<target)
                left++;
            else
                return  new int[]{++left,++right};
        }
        return null;
        //2.双指针？  滑动窗口？  时间复杂度 O(n)
        /* 题解：
                进入循环的条件 ：left<right
                单步操作:  sum < target    left ++  sum > target right--
                终止操作：numbers[left] + numbers[right] == target*/
       /* int left = 0,right = numbers.length-1,sum;
        while (left<right){
            sum = numbers[left]+numbers[right];
            if(sum==target)  return new int[]{++left,++right};
            if(sum>target)right--;
            else  left++;
        }
        return null;*/

        //1.HashMap存储： <target-numbers[i],i+1> ,依次遍历是否存在key  .时间、空间复杂度 O(n)
       /* Map<Integer,Integer>  map = new HashMap<>();
        int length = numbers.length;
        for (int i = 0; i < length; i++) {
            if(map.containsKey(numbers[i]))
                return new int[]{map.get(numbers[i]),i+1};
            map.put(target-numbers[i],i+1);
        }
        return null;*/
    }
}
